package com.LeeCode;

import java.util.Arrays;

/**
 * 最小化数对的最大差值
 */

public class Code2616 {
    public static void main(String[] args) {
        int[] nums = {4, 2, 1, 2};
        int p = 1;
        System.out.println(new Code2616().minimizeMax(nums, p));
    }

    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int n = nums.length;
        int left = -1, right = nums[n - 1] - nums[0];

        while (left + 1 < right) {
            int mid = (left + right) >> 1;

            if (canFormPairs(nums, p, mid)) {
                right = mid; // 尝试更小的答案
            } else {
                left = mid; // 当前 mid 不够大，需要更大
            }
        }

        return right;
    }

    private boolean canFormPairs(int[] nums, int p, int maxDiff) {
        int count = 0;
        for (int i = 1; i < nums.length; ) {
            if (nums[i] - nums[i - 1] <= maxDiff) {
                count++;
                i += 2; // 使用了两个元素，跳过下一个
            } else {
                i++; // 继续找下一对
            }
        }
        return count >= p;
    }
}
